#example code, lecture 4
#functions
def sqrt(x):
    """function documentation"""
    ans = 0
    if x >= 0:
        while ans*ans < x:
            ans = ans + 1
        if ans*ans != x:
            print x , 'is not a perfect square'
            return None
        else: return ans
    else:
        print x, 'is a negative number'
        return None

#print sqrt( 16 )
def f( x ):
    x = x + 1
    return x

#how many pigs and chickens in the yard
def solve( numlegs, numheads ):
    for numChicks in range( 0,numheads+1 ):
        numPigs = numheads - numChicks
        totallegs = 2*numChicks+4*numPigs
        if totallegs == numlegs:
            return (numPigs, numChicks)
    return (None, None)

def barnYard():
    heads = int( raw_input( 'Enter numbers of heads:' ) )
    legs = int( raw_input('Enter numbers of legs:' ))
    pigs,chickens = solve( legs,heads )
    if pigs == None:
        print 'There is no solution'
    else:
        print 'Number of pigs:', pigs
        print 'Number of chickens:', chickens

#barnYard()
def solve1( numlegs, numheads ):
    for numSpiders in range( 0,numheads+1 ):
        for numChicks in range( 0,numheads-numSpiders+1 ):
            numPigs = numheads - numSpiders - numChicks
            totallegs = 2*numChicks+4*numPigs+8*numSpiders
            if totallegs == numlegs:
                return (numPigs, numChicks, numSpiders)
    return (None, None, None)

def solve2( numlegs, numheads ):
    solutionFound = False
    for numSpiders in range( 0,numheads+1 ):
        for numChicks in range( 0,numheads-numSpiders+1 ):
            numPigs = numheads - numSpiders - numChicks
            totallegs = 2*numChicks+4*numPigs+8*numSpiders
            if totallegs == numlegs:
                print 'Number of pigs:'+ str( numPigs ) + ','
                print 'Number of chickens:'+ str( numChicks ) + ','
                print 'Number of spiders:'+ str( numSpiders )
                solutionFound = True
                #return (numPigs, numChicks, numSpiders)
    if not solutionFound: print 'There is no solution'

def barnYard1():
    heads = int( raw_input( 'Enter numbers of heads:' ) )
    legs = int( raw_input('Enter numbers of legs:' ))
    pigs,chickens,spiders = solve1( legs,heads )
    if pigs == None:
        print 'There is no solution'
    else:
        print 'Number of pigs:', pigs
        print 'Number of chickens:', chickens
        print 'Number of spiders:', spiders

#barnYard1()
#solve2( 140,30 )

def isPalindrome(s):
    """return True if is a palindrome and False otherwise"""
    if len(s) <= 1: return True
    else: return s[ 0 ]== s[ -1 ] and isPalindrome( s[1:-1] )

#print isPalindrome('isasi')
#print isPalindrome('isabsi')

def isPalindrome1(s,indent):
    """Return True if s is a palidrome and False otherwise"""
    print indent, 'isPalindrome1 called with', s
    if len( s ) <= 1:
        print indent, 'About to return True from base case'
        return True
    else:
        ans = s[ 0 ] == s[ -1 ] and isPalindrome1(s[ 1:-1 ],indent + indent)
        print indent, 'About to return', ans
        return ans
#print isPalindrome1('abceedcba', ' ')

def fib( x ):
    """return fibonacci number, where x is non-negative int """
    if x == 1 or x == 0:
        return 1
    else:
        return fib( x-1 )+fib( x-2 )
print fib( 12 )
